package com.company.剑指offer每日刷题.专项版;


import java.util.HashSet;
import java.util.Set;

/**
 * 剑指 Offer 38. 字符串的排列
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 * 示例:
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 * */
public class permutation {
    /**
     * 思路 ：回溯法
     * */

    public static void main(String[] args) {
        permutation p = new permutation();
        String[] abcs = p.permutation("f");
        for (int i = 0; i <abcs.length; i++) {
            System.out.println(abcs[i]);
        }
    }


    public String[] permutation(String s){
        char[][] visited = new char[s.length()][2];
        //提取所有字符
        for(int i=0;i<s.length();i++){
            visited[i][0] =  s.charAt(i);
            visited[i][1] = 'n';
        }
        HashSet<String> resList = new HashSet<>();
        backTracking(visited,0,new StringBuilder(""),resList);
        return resList.toArray(new String[resList.size()]);
    }
    public void backTracking(char[][] visited, int visitedCount, StringBuilder stringBuilder, Set<String> reslist){
        //收集结果
        if(visitedCount == visited.length){
            reslist.add(stringBuilder.toString());
            return;
        }
        //搜索
        for (int i = 0; i < visited.length; i++) {
            if(visited[i][1] == 'n'){
                stringBuilder.append(visited[i][0]);
                visitedCount++;
                visited[i][1]='y';
                backTracking(visited,visitedCount,stringBuilder,reslist);
                //回溯结果
                stringBuilder.deleteCharAt(stringBuilder.length() -1);
                visited[i][1]='n';
                visitedCount--;
            }
        }
    }
}
